// https://leetcode.cn/problems/find-all-anagrams-in-a-string/

// 题干：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，
//      返回这些子串的起始索引。不考虑答案输出的顺序。
//      异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

// 示例：输入: s = "cbaebabacd", p = "abc"
//       输出: [0,6]

// 碎语：先解决一个小问题，如何快速判断两个字符串是否是“异位词”
//       1.先按字典序排列，最后再比较，但是这种时间复杂度太高了，可以看出来排序是一个无关紧要的过程
//       2.因此不考虑顺序，只需要考虑三个字符出现的次数，利用哈希表即可
//       遍历一个字符串，把每个字符丢到哈希表里面，再把另外一个字符串丢到另一个哈希表再来比对

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    vector<int> ret;
public:
    vector<int> findAnagrams(string s, string p)
    {
        // 我们发现第二次枚举的时候，不需要全部把上一次枚举的字符全部移除，只需要移除一个，加入一个即可
        // 滑动窗口 + 哈希表
        // 怎么更新结果的判断条件？
        // 利用变量count来统计窗口中“有效字符”的个数

        if (s.size() < p.size()) return {};

        int hash1[26] = {0}; // 统计p字符里面字符出现的次数
        for (const auto& ch : p) hash1[ch - 'a']++;

        int hash2[26] = {0}; // 统计滑动窗口里面每一个字符出现的个数
        for (int left = 0, right = 0, count = 0 ; right < s.size() ; right++){
            char in = s[right];
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++; // 进窗口 + 维护count变量

            if (right - left + 1 > p.size()){ // 判断
                char out = s[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--; // 出窗口 + 维护count变量
            }

            if (count == p.size()) ret.push_back(left);
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    string s = "cbaebabacd";
    string p = "abc";

    vector<int> index = sol.findAnagrams(s, p);
    for (const auto& num : index) cout << num << " ";
    
    return 0;
}













